import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 三石
 * Date: 2022-04-25
 * Time: 15:56
 */
class Node{
    public int date;
    public Node next;

    public Node(int date){
        this.date=date;
        this.next=null;
    }
}
public class Mylinkedlist {
    public Node head;  //保存单链表的头节点的引用 null

    //头插法
    public void addFirst(int date) {
        Node node = new Node(date);
        if (this.head == null) {
            //第一次插入
            this.head = node;
            return;
        }
        node.next = this.head;
        this.head = node;
    }

    //打印链表
    public void display() {
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.date + " ");
            cur = cur.next;
        }
    }

    //尾插法
    public void addLast(int date){
        Node node=new Node(date);
        if(this.head==null){
            this.head=node;
            return;
        }
        Node cur=this.head;
        while (cur.next!=null){  //cur从头开始，一直往后走，直到找到null
            cur=cur.next;
        }
        cur.next=node;          //将node的地址赋给cur
    }

    //查找是否包含关键字key在链表中
    public boolean contains(int key){

        Node cur=this.head;
        while (cur.next!=null){
            if(key==cur.date){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }


    //计算链表的长度
    public int size(){
        int count=0;
        Node cur=this.head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }


    private Node searchIndex(int index){
        if(index<0||index>size()){
            throw new RuntimeException("index位置不合法！");
        }
        Node cur=this.head;  //index-1
          while (index-1!=0){
              cur=cur.next;
              index--;
          }
          return cur;
    }


    //任意位置插入
    public void addIndex(int index,int date){//定义一个cur=index-1，index是插入的地址（第几个节点）
        Node node=new Node(date);
        if (index == 0) {   //相当于头插法
          addFirst(date);
          return;
        }
        if(index==size()){   //相当于尾插
         addLast(date);
         return;
        }
        //如果不是头尾插，需要找到index的前一个节点的地址
        Node cur=searchIndex( index);
        //Node node=new Node(date);
                node.next=cur.next;
                cur.next=node;
    }
}
